package com.study.algorithm.datastruct.graph.impl;

import com.study.algorithm.datastruct.graph.GraphOperate;
import com.study.algorithm.datastruct.graph.model.Edge;
import com.study.algorithm.datastruct.graph.model.Graph;
import com.study.algorithm.datastruct.graph.model.Vertex;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.stream.Collectors;

public class GraphOperateImpl extends GraphBasicOperateImpl implements GraphOperate {
    @Override
    public boolean isExistPathFromVertexToVertex(Graph graph, Vertex start, Vertex end) {
        return searchPathAndReturnFromVertexToVertex(graph, start, end, false) != null;
    }

    @Override
    public List<Vertex> getOnePathFromVertexToVertex(Graph graph, Vertex start, Vertex end) {
        return searchPathAndReturnFromVertexToVertex(graph, start, end, false)
                .stream()
                .collect(Collectors.toList());
    }

    @Override
    public List<Vertex> getOnePathFromVertexToVertex(Graph graph, Vertex start, Vertex end
            , boolean isDepthFirst) {
        return searchPathAndReturnFromVertexToVertex(graph, start, end, isDepthFirst)
                .stream()
                .collect(Collectors.toList());
    }

    /**
     * @param graph        需要探索的图
     * @param start        开始节点（入口）
     * @param end          结束节点（出口)
     * @param isDepthFirst 是否使用深度优先遍历（默认使用广度优先)
     * @return 路径节点轨迹（由于是栈结构，所以顶端存放的是出口，低端存放的是入口)
     */
    private Stack<Vertex> searchPathAndReturnFromVertexToVertex(Graph graph, Vertex start, Vertex end
            , boolean isDepthFirst) {
        Vertex startVertex = containVertexAndReturnVertex(graph, start);
        Vertex endVertex = containVertexAndReturnVertex(graph, end);
        if (startVertex == null || endVertex == null) {
            return new Stack<>();
        }

        //采用广度优先
//        return searchPathThroughBreadthFirst(graph, startVertex, endVertex);
        //深度优先
        return isDepthFirst ? searchPathThroughDepthFirst(graph, startVertex, endVertex)
                : searchPathThroughBreadthFirst(graph, startVertex, endVertex);


    }

    /**
     * 深度优先
     * <p>
     * 写Djksla最短路径的时候突然回味，原来我这是采用的深度优先算法的思想（不撞南墙不回头），
     * 另外我的想法还是优化版的深度优先，解决了某一点多次探索的问题
     * 不同数据结构构建的树，写法不一致，思想可借鉴
     *
     * @param graph       需要探索的图
     * @param startVertex 开始节点（入口）
     * @param endVertex   结束节点（出口)
     * @return 路径节点轨迹（由于是栈结构，所以顶端存放的是出口，低端存放的是入口)
     */
    private Stack<Vertex> searchPathThroughDepthFirst(Graph graph, Vertex startVertex, Vertex endVertex) {

        //使用栈存储正在探测的顶点，可以使探测步骤有序进行，而不是随机探测
        Stack<Vertex> vertices = new Stack<>();
        //使用标记以XX为起点，等待探测的边
        Map<Vertex, Set<Edge>> edgeMap = new HashMap<>();
        //下边两个变量是为了防止重复探测使用（已经探测的边和探测完毕的点，不会再重复探测)
        Set<Edge> visitedEdge = new HashSet<>();
        Set<Vertex> visitedVertex = new HashSet<>();
        Set<Edge> startEdges = queryEdgesUsingTheStartVertex(graph, startVertex);
        boolean isFound = false;
        if (startEdges == null || startEdges.size() == 0) {
            return vertices;
        }


        edgeMap.put(startVertex, startEdges);
        vertices.push(startVertex);
        //上边一堆准备工作，下面开始执行
        while (!vertices.isEmpty()) {
            //找到下一个要探测的点，改点已经保存在vertices，返回的结果是用来判断是否为目标终点
            isFound = searchNextVertexMayArriveVertex(graph, vertices, edgeMap, endVertex, visitedEdge, visitedVertex);
            if (isFound) {
                //目标终点已经找到，结束探测
                break;
            }
        }
        //目标终点找到，同时探测轨迹栈不为空，说明已经成功探测到目标点
        //目标终点找到，探测轨迹栈为空，该情况不会发生，只是为了逻辑贯通才这么写
        if (isFound && !vertices.isEmpty()) {
            return vertices;
        }
        return new Stack<>();
    }

    /**
     * 广度优先
     * <p>
     *
     * @param graph       需要探索的图
     * @param startVertex 开始节点（入口）
     * @param endVertex   结束节点（出口)
     * @return 路径节点轨迹（由于是栈结构，所以顶端存放的是出口，低端存放的是入口)
     */
    private Stack<Vertex> searchPathThroughBreadthFirst(Graph graph, Vertex startVertex, Vertex endVertex) {

        //使用堆存储正在探测的顶点，探测顺序：兄弟节点>孩子节点
        Queue<Vertex> vertexQueue = new LinkedBlockingQueue<>();

        //用于记录前驱节点，时光回溯路径
        Map<Vertex, Vertex> preVertexMap = new HashMap<>();
        //下边两个变量是为了防止重复探测使用（已经探测的边和探测完毕的点，不会再重复探测)
        Set<Edge> visitedEdge = new HashSet<>();
        Set<Vertex> visitedVertex = new HashSet<>();
        boolean isFound = false;
        vertexQueue.add(startVertex);
        //上边一堆准备工作，下面开始执行
        while (!vertexQueue.isEmpty()) {
            Vertex currStartVertex = vertexQueue.poll();
            Set<Edge> edgeSet = queryEdgesUsingTheStartVertex(graph, currStartVertex);
            //找到下一个要探测的点,由于广度遍历不需要递归，所以下一个需要查询的点由该层给出
            isFound = matchAllEndVertexWithCurrStartVertex(vertexQueue, preVertexMap, edgeSet, endVertex, visitedEdge, visitedVertex);
            if (isFound) {
                //目标终点已经找到，结束探测
                break;
            }
        }

        return isFound ?
                getThePathThroughBackTrace(preVertexMap, startVertex, endVertex)
                : new Stack<>();
    }

    /**
     * 通过回溯法找到节点访问路径
     *
     * @param preVertexMap 前驱节点map，key是子节点，value是父节点（前驱)
     * @param startVertex  路径开始节点
     * @param endVertex    路径结束节点
     * @return 节点访问路径（栈低是入口（起始节点）,栈顶是出口（结束节点)
     */
    public Stack<Vertex> getThePathThroughBackTrace(Map<Vertex, Vertex> preVertexMap, Vertex startVertex, Vertex endVertex) {
        Stack<Vertex> traceStack = new Stack<>();
        if (preVertexMap == null || startVertex.equals(endVertex)) {
            return traceStack;
        }

        List<Vertex> traces = new ArrayList<>();
        traces.add(endVertex);
        Vertex currEndVertex = endVertex;
        while (!preVertexMap.isEmpty()) {
            currEndVertex = preVertexMap.get(currEndVertex);
            if (currEndVertex == null) {
                break;
            }
            traces.add(currEndVertex);
            if (startVertex.equals(currEndVertex)) {
                break;
            }
        }
        //采用入口在栈低，是为了跟深度遍历保持一致（不直接返回list，也是由于该原因)
        for (int index = traces.size() - 1; index >= 0; index--) {
            traceStack.add(traces.get(index));
        }
        return traceStack;

    }


    /**
     * 该函数为广度优先遍历的递归探测子节点的函数
     *
     * @param vertexQueue   将要探测的顶点集合
     * @param preVertexMap  记录前驱节点，用于时光回溯，记录路径
     * @param edgeSet       以正在探测的顶点为起点的边
     * @param endVertex     需要探测的顶点
     * @param visitedEdge   对探测过的边标记，表示该边已经探测过，不要在重复探测了
     * @param visitedVertex 对已经探测完毕的点和已经入队列等待探测的点的集合，不需要重复入探测队列
     * @return 是否找到了目的顶点
     */
    private boolean matchAllEndVertexWithCurrStartVertex(Queue<Vertex> vertexQueue,
                                                         Map<Vertex, Vertex> preVertexMap,
                                                         Set<Edge> edgeSet,
                                                         Vertex endVertex,
                                                         Set<Edge> visitedEdge,
                                                         Set<Vertex> visitedVertex) {

        boolean isFound = false;
        if (edgeSet == null || edgeSet.size() == 0) {
            return isFound;
        }

        for (Edge edge : edgeSet) {
            Vertex currEndVertex = edge.getEndVetex();
            if (endVertex.equals(currEndVertex)) {
                preVertexMap.put(currEndVertex, edge.getStartVetex());
                isFound = true;
                return isFound;
            }
            if (visitedEdge.contains(edge)) {
                continue;
            }
            visitedEdge.add(edge);
            if (visitedVertex.contains(currEndVertex)) {
                continue;
            }
            visitedVertex.add(currEndVertex);
            vertexQueue.add(currEndVertex);
            preVertexMap.put(currEndVertex, edge.getStartVetex());
        }

        return isFound;
    }


    /**
     * 该函数为深度遍历的递归探测子节点的函数
     *
     * @param graph         要探测的图
     * @param excludeVertex 正在探测的顶点，再遇到这里面的点，就绕开
     * @param edgeMap       以正在探测的顶点为起点边，但是还未探测的
     * @param endVertex     需要探测的顶点
     * @param visitedEdge   对探测过的边标记，表示该边已经探测过，不要在重复探测了
     * @param visitedVertex 对已经探测完毕的点进行标记，表示以该点为起点的边已经探测完毕，不要在重复探测了
     * @return 是否找到了目的顶点
     */
    private boolean searchNextVertexMayArriveVertex(Graph graph, Stack<Vertex> excludeVertex,
                                                    Map<Vertex, Set<Edge>> edgeMap,
                                                    Vertex endVertex,
                                                    Set<Edge> visitedEdge,
                                                    Set<Vertex> visitedVertex) {

        boolean isFound = false;
        Vertex nextVertex = null;
        if (excludeVertex.isEmpty()) {
            return isFound;
        }

        Vertex startVertex = excludeVertex.peek();
        Set<Edge> startEdges = edgeMap.get(startVertex);
        //常规性检测，一般不会发生
        if (startEdges == null || startEdges.size() == 0) {
            edgeMap.remove(startEdges);
            excludeVertex.pop();
            return isFound;
        }

        Iterator<Edge> it = startEdges.iterator();
        //找到还未探测的，并以当前正在探测的点为起点的边的顶点
        //当使用迭代器的时候，如果移除其中元素，需要给迭代器重新赋值，否则会出错
        while (it.hasNext()) {
            Edge currEdge = it.next();
            //判断当前找到的边是否探测过，如果已经探测过，绕过
            if (visitedEdge.contains(currEdge)) {
                startEdges.remove(currEdge);
                it = startEdges.iterator();
                continue;
            }
            //将该边标记已经访问过
            visitedEdge.add(currEdge);
            Vertex currEndVertex = currEdge.getEndVetex();
            //发现目标点，返回
            if (endVertex.equals(currEndVertex)) {
                excludeVertex.push(currEndVertex);
                isFound = true;
                return isFound;
            }

            //判断当前探测的点是否已经探测完毕或者正在探测，是的话，下一条边，绕过该边
            if (visitedVertex.contains(currEndVertex) ||
                    excludeVertex.contains(currEndVertex)) {
                startEdges.remove(currEdge);
                it = startEdges.iterator();
                continue;
            }

            //找到下一个需要探测的点
            nextVertex = currEndVertex;
            break;
        }

        if (nextVertex != null) {
            excludeVertex.push(nextVertex);
            edgeMap.put(nextVertex, queryEdgesUsingTheStartVertex(graph, nextVertex));
            return searchNextVertexMayArriveVertex(graph, excludeVertex, edgeMap, endVertex, visitedEdge, visitedVertex);
        }
        //迭代器已经空了，也没有找到下一个节点，说明以该顶点为起始顶点已经被探测完了
        excludeVertex.pop();
        edgeMap.remove(startVertex);
        visitedVertex.add(startVertex);
        return isFound;
    }

}
